#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
#include <queue>
//class Solution {
//public:
//    //vector<vector<int>> visit;
//    int m, n;
//    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
//        m = maze.size();
//        n = maze[0].size();
//        //visit.resize(m,vector<int>(n,0));
//        return bfs(maze, entrance[0], entrance[1]);
//    }
//    int dx[4] = { 1,-1,0,0 };
//    int dy[4] = { 0,0,1,-1 };
//    int bfs(vector<vector<char>>& maze, int i, int j)
//    {
//        int ret = 0;
//        queue<pair<int, int>> q;
//        q.push(make_pair(i, j));
//        maze[i][j] = '+';
//        int flag = 0;
//        for (int i = 0; i < n; i++)
//        {
//            if (maze[0][i] == '.')
//            {
//                flag = 1;
//                break;
//            }
//            if (maze[m - 1][i] == '.')
//            {
//                flag = 1;
//                break;
//            }
//        }
//        for (int i = 1; i < m - 1; i++)
//        {
//            if (maze[i][0] == '.')
//            {
//                flag = 1;
//                break;
//            }
//            if (maze[i][n - 1] == '.')
//            {
//                flag = 1;
//                break;
//            }
//        }
//        if (flag == 0)
//            return -1;
//        int prevx = 0;
//        int prevy = 0;
//        while (!q.empty())
//        {
//            //auto [a, b] = q.front();
//            //if (ret == 5)
//            //    int i = 0;
//            int size = q.size();
//
//            ret++;
//            int flag1 = 0;
//            for (int i = 0; i < size; i++)
//            {
//                if (ret == 7)
//                    int i = 0;
//                int a = q.front().first;
//                int b = q.front().second;
//                prevx = a;
//                prevy = b;
//                q.pop();
//                for (int k = 0; k < 4; k++)
//                {
//                    int x = a + dx[k];
//                    int y = b + dy[k];
//                    if (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.')
//                    {
//                       
//                        if (x == 0 || x == m - 1 || y == 0 || y == n - 1)
//                        {
//                            prevx = x;
//                            prevy = y;
//                            flag1 = 1;
//                            break;
//                        }
//                        maze[x][y] = '+';
//                        q.push(make_pair(x, y));
//                    }
//                }
//                if (flag1)
//                    break;
//            }
//            if (flag1)
//                break;
//        }
//        if (prevx == i && prevy == j)
//            return -1;
//        if (prevx == 0 || prevx == m - 1 || prevy == 0 || prevy == n - 1)
//            return ret == 0 ? -1 : ret;
//        return -1;
//    }
//};
#include <unordered_map>
//class Solution {
//public:
//    int minMutation(string startGene, string endGene, vector<string>& bank) {
//        unordered_map<string, int> hash1;
//        unordered_map<string, int> hash2;
//        char arr[4] = { 'A','C','G','T' };
//        for (auto& e : bank)
//            hash1[e]++;
//        queue<string> q;
//        q.push(startGene);
//        hash2[startGene]++;
//        int flag = 0;
//        int ret = 0;
//        while (!q.empty())
//        {
//            int size = q.size();
//
//            ret++;
//            for (int k = 0; k < size; k++)
//            {
//                string tmp = q.front();
//                q.pop();
//                for (int i = 0; i < tmp.size(); i++)
//                {
//                    if (i == tmp.size() - 1)
//                        int i = 0;
//                    char prev = tmp[i];
//                    for (int j = 0; j < 4; j++)
//                    {
//                        if (arr[j] != prev)
//                        {
//                            tmp[i] = arr[j];
//                            if (hash1.count(tmp) && hash2.count(tmp) == 0)
//                            {
//                                q.push(tmp);
//                                hash2[tmp]++;
//                                if (tmp == endGene)
//                                {
//                                    flag = 1;
//                                    break;
//                                }
//                            }
//                        }
//                    }
//                    tmp[i] = prev;
//                    if (flag)
//                        break;
//                }
//                if (flag)
//                    break;
//            }
//            if (flag)
//                break;
//
//        }
//        return hash2.count(endGene) == 0 ? -1 : ret;
//    }
//};
//class Solution {
//public:
//    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
//        unordered_map<string, int> visit;
//        unordered_map<string, int> hash;
//        for (auto& e : wordList)
//            hash[e];
//        if (beginWord == endWord)
//            return 1;
//        if (hash.count(endWord) == 0)
//            return 0;
//        queue<string> q;
//        q.push(beginWord);
//        visit[beginWord];
//        int ret = 1;
//        while (!q.empty())
//        {
//            int size = q.size();
//            ret++;
//            for (int i = 0; i < size; i++)
//            {
//                string tmp = q.front();
//                q.pop();
//                for (int j = 0; j < tmp.size(); j++)
//                {
//                    char prev = tmp[j];
//                    for (int k = 0; k < 26; k++)
//                    {
//                        char ch = 'a' + k;
//                        if (ch != prev)
//                        {
//                            tmp[j] = ch;
//                            if (visit.count(tmp) == 0 && hash.count(tmp))
//                            {
//                                visit[tmp];
//                                q.push(tmp);
//                                if (tmp == endWord)
//                                    return ret;
//                            }
//                        }
//                    }
//                    tmp[j] = prev;
//                }
//            }
//        }
//        return 0;
//    }
//};

//class Solution {
//public:
//    struct Com
//    {
//        bool operator()(const pair<int, pair<int, int>>& l, const pair<int, pair<int, int>>& r)
//        {
//            return l.first < r.first;
//        }
//    };
//    int dx[4] = { 1,-1,0,0 };
//    int dy[4] = { 0,0,1,-1 };
//    int cutOffTree(vector<vector<int>>& forest) {
//        int m = forest.size();
//        int n = forest[0].size();
//        vector<pair<int, pair<int, int>>> v;
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                v.push_back(make_pair(forest[i][j], make_pair(i, j)));
//            }
//        }
//        Com com;
//        sort(v.begin(), v.end(), com);
//        int previ = 0;
//        int nexti = 1;
//        int ret = 0;
//        for (; previ < v.size() - 1; previ++,nexti++)
//        {
//            if (v[previ].first == 0)
//                continue;
//            queue<pair<int, int>> q;
//            q.push(v[previ].second);
//            int flag = 0;
//            while (!q.empty())
//            {
//                int size = q.size();
//                ret++;
//                for (int i = 0; i < size; i++)
//                {
//                    //auto [a, b] = q.front();
//                    int a = q.front().first;
//                    int b = q.front().second;
//                    q.pop();
//                    for (int j = 0; j < 4; j++)
//                    {
//                        int x = a + dx[j];
//                        int y = b + dy[j];
//                        if (x >= 0 && x < m && y >= 0 && y < n && forest[i][j] != 0)
//                        {
//                            q.push(make_pair(x, y));
//                            if (make_pair(x, y) == v[nexti].second)
//                            {
//                                flag = 1;
//                                break;
//                            }
//                        }
//                        if (flag)
//                            break;
//                    }
//                    if (flag)
//                        break;
//                }
//                if (flag)
//                    break;
//            }
//            pair<int, int> tmp = q.back();
//            if (forest[tmp.first][tmp.second] != v[nexti].first)
//                return -1;
//        }
//        return ret;
//
//    }
//
//};

class Solution {
public:
    struct Com
    {
        bool operator()(const pair<int, pair<int, int>>& l, const pair<int, pair<int, int>>& r)
        {
            return l.first < r.first;
        }
    };
    int dx[4] = { 1,-1,0,0 };
    int dy[4] = { 0,0,1,-1 };
    int m, n;
    vector<vector<bool>> visit;
    int cutOffTree(vector<vector<int>>& forest) {
        m = forest.size();
        n = forest[0].size();
        visit.resize(m, vector<bool>(n, true));
        vector<pair<int, pair<int, int>>> v;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (forest[i][j] != 0 && forest[i][j] != 1)
                    v.push_back(make_pair(forest[i][j], make_pair(i, j)));
            }
        }
        Com com;
        sort(v.begin(), v.end(), com);
        int bx = 0, by = 0;
        int ret = 0;
        for (int i = 0; i < v.size(); i++)
        {
            auto [a, b] = v[i].second;
            int step = bfs(forest, bx, by, a, b);
            if (step == -1)
                return -1;
            ret += step;
            bx = a;
            by = b;
        }
        return ret;
    }
    int bfs(vector<vector<int>>& forest, int bx, int by, int a, int b)
    {
        if (bx == a && by == b)
            return 0;
        int ret = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                visit[i][j] = true;
            }
        }
        queue<pair<int, int>> q;
        q.push(make_pair(bx, by));
        visit[bx][by] = false;
        while (!q.empty())
        {
            int size = q.size();
            ret++;
            for (int i = 0; i < size; i++)
            {
                auto [a1, b1] = q.front();
                q.pop();
                for (int j = 0; j < 4; j++)
                {
                    int x = a1 + dx[j];
                    int y = b1 + dy[j];
                    if (x >= 0 && x < m && y >= 0 && y < n && visit[x][y] && forest[x][y])
                    {
                        visit[x][y] = false;
                        q.push(make_pair(x, y));
                        if (x == a && y == b)
                            return ret;
                    }
                }
            }

        }
        return -1;
    }

};
int main()
{
    //vector<vector<char>> maze = { {'+','.','+','+','+','+','+'},
    //                              {'+','.','+','.','.','.','+'},
    //                              {'+','.','+','.','+','.','+'},
    //                              {'+','.','.','.','.','.','+'},
    //                              {'+','+','+','+','.','+','.'}};
    //vector<int> entrance = { 0,1 };
    //Solution().nearestExit(maze, entrance);
    //string start("AACCGGTT");
    //string end("AACCGGTA");
    //vector<string> t = { "AACCGGTA" };
    //cout<<Solution().minMutation(start, end, t);
    //string start("hit");
    //string end("cog");
    //vector<string> v = { "hot","dot","dog","lot","log","cog" };
    //Solution().ladderLength(start, end, v);
    vector<vector<int>> forest = { {54581641, 64080174, 24346381, 69107959},{86374198, 61363882, 68783324, 79706116},{668150, 92178815, 89819108, 94701471},{83920491, 22724204, 46281641, 47531096},{89078499, 18904913, 25462145, 60813308} };
    Solution().cutOffTree(forest);
    return 0;
}